home *** CD-ROM | disk | FTP | other *** search
/ Linux Cubed Series 4: GNU Archives / Linux Cubed Series 4 - GNU Archives.iso / gnu / findutil.1 / findutil / findutils-4.1 / find / find.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-10-12  |  14.7 KB  |  542 lines
  1. /* find -- search for files in a directory hierarchy
  2.    Copyright (C) 1990, 91, 92, 93, 94 Free Software Foundation, Inc.
  3.  
  4.    This program is free software; you can redistribute it and/or modify
  5.    it under the terms of the GNU General Public License as published by
  6.    the Free Software Foundation; either version 2, or (at your option)
  7.    any later version.
  8.  
  9.    This program is distributed in the hope that it will be useful,
  10.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12.    GNU General Public License for more details.
  13.  
  14.    You should have received a copy of the GNU General Public License
  15.    along with this program; if not, write to the Free Software
  16.    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.  */
  17.  
  18. /* GNU find was written by Eric Decker <cire@cisco.com>,
  19.    with enhancements by David MacKenzie <djm@gnu.ai.mit.edu>,
  20.    Jay Plett <jay@silence.princeton.nj.us>,
  21.    and Tim Wood <axolotl!tim@toad.com>.
  22.    The idea for -print0 and xargs -0 came from
  23.    Dan Bernstein <brnstnd@kramden.acf.nyu.edu>.  */
  24.  
  25. #include <config.h>
  26. #include <sys/types.h>
  27. #include <sys/stat.h>
  28. #include <stdio.h>
  29. #ifdef HAVE_FCNTL_H
  30. #include <fcntl.h>
  31. #else
  32. #include <sys/file.h>
  33. #endif
  34. #include "defs.h"
  35. #include "modetype.h"
  36.  
  37. #ifndef S_IFLNK
  38. #define lstat stat
  39. #endif
  40.  
  41. int lstat ();
  42. int stat ();
  43.  
  44. #define apply_predicate(pathname, stat_buf_ptr, node)    \
  45.   (*(node)->pred_func)((pathname), (stat_buf_ptr), (node))
  46.  
  47. static void process_top_path P_((char *pathname));
  48. static int process_path P_((char *pathname, char *name, boolean leaf, char *parent));
  49. static void process_dir P_((char *pathname, char *name, int pathlen, struct stat *statp, char *parent));
  50. static boolean no_side_effects P_((struct predicate *pred));
  51.  
  52. /* Name this program was run with. */
  53. char *program_name;
  54.  
  55. /* All predicates for each path to process. */
  56. struct predicate *predicates;
  57.  
  58. /* The last predicate allocated. */
  59. struct predicate *last_pred;
  60.  
  61. /* The root of the evaluation tree. */
  62. static struct predicate *eval_tree;
  63.  
  64. /* If true, process directory before contents.  True unless -depth given. */
  65. boolean do_dir_first;
  66.  
  67. /* If >=0, don't descend more than this many levels of subdirectories. */
  68. int maxdepth;
  69.  
  70. /* If >=0, don't process files above this level. */
  71. int mindepth;
  72.  
  73. /* Current depth; 0 means current path is a command line arg. */
  74. int curdepth;
  75.  
  76. /* Seconds between 00:00 1/1/70 and either one day before now
  77.    (the default), or the start of today (if -daystart is given). */
  78. time_t cur_day_start;
  79.  
  80. /* If true, cur_day_start has been adjusted to the start of the day. */
  81. boolean full_days;
  82.  
  83. /* If true, do not assume that files in directories with nlink == 2
  84.    are non-directories. */
  85. boolean no_leaf_check;
  86.  
  87. /* If true, don't cross filesystem boundaries. */
  88. boolean stay_on_filesystem;
  89.  
  90. /* If true, don't descend past current directory.
  91.    Can be set by -prune, -maxdepth, and -xdev/-mount. */
  92. boolean stop_at_current_level;
  93.  
  94. #ifndef HAVE_FCHDIR
  95. /* The full path of the initial working directory.  */
  96. char *starting_dir;
  97. #else
  98. /* A file descriptor open to the initial working directory.
  99.    Doing it this way allows us to work when the i.w.d. has
  100.    unreadable parents.  */
  101. int starting_desc;
  102. #endif
  103.  
  104. /* If true, we have called stat on the current path. */
  105. boolean have_stat;
  106.  
  107. /* The file being operated on, relative to the current directory.
  108.    Used for stat, readlink, and opendir.  */
  109. char *rel_pathname;
  110.  
  111. /* Length of current path. */
  112. int path_length;
  113.  
  114. /* true if following symlinks.  Should be consistent with xstat.  */
  115. boolean dereference;
  116.  
  117. /* Pointer to the function used to stat files. */
  118. int (*xstat) ();
  119.  
  120. /* Status value to return to system. */
  121. int exit_status;
  122.  
  123. #ifdef DEBUG_STAT
  124. static int
  125. debug_stat (file, bufp)
  126.      char *file;
  127.      struct stat *bufp;
  128. {
  129.   fprintf (stderr, "debug_stat (%s)\n", file);
  130.   return lstat (file, bufp);
  131. }
  132. #endif /* DEBUG_STAT */
  133.  
  134. void
  135. main (argc, argv)
  136.      int argc;
  137.      char *argv[];
  138. {
  139.   int i;
  140.   PFB parse_function;        /* Pointer to who is to do the parsing. */
  141.   struct predicate *cur_pred;
  142.   char *predicate_name;        /* Name of predicate being parsed. */
  143.  
  144.   program_name = argv[0];
  145.  
  146.   predicates = NULL;
  147.   last_pred = NULL;
  148.   do_dir_first = true;
  149.   maxdepth = mindepth = -1;
  150.   cur_day_start = time ((time_t *) 0) - DAYSECS;
  151.   full_days = false;
  152.   no_leaf_check = false;
  153.   stay_on_filesystem = false;
  154.   exit_status = 0;
  155.   dereference = false;
  156. #ifdef DEBUG_STAT
  157.   xstat = debug_stat;
  158. #else /* !DEBUG_STAT */
  159.   xstat = lstat;
  160. #endif /* !DEBUG_STAT */
  161.  
  162. #ifdef DEBUG
  163.   printf ("cur_day_start = %s", ctime (&cur_day_start));
  164. #endif /* DEBUG */
  165.  
  166.   /* Find where in ARGV the predicates begin. */
  167.   for (i = 1; i < argc && strchr ("-!(),", argv[i][0]) == NULL; i++)
  168.     /* Do nothing. */ ;
  169.  
  170.   /* Enclose the expression in `( ... )' so a default -print will
  171.      apply to the whole expression. */
  172.   parse_open (argv, &argc);
  173.   /* Build the input order list. */
  174.   while (i < argc)
  175.     {
  176.       if (strchr ("-!(),", argv[i][0]) == NULL)
  177.     usage ("paths must precede expression");
  178.       predicate_name = argv[i];
  179.       parse_function = find_parser (predicate_name);
  180.       if (parse_function == NULL)
  181.     error (1, 0, "invalid predicate `%s'", predicate_name);
  182.       i++;
  183.       if (!(*parse_function) (argv, &i))
  184.     {
  185.       if (argv[i] == NULL)
  186.         error (1, 0, "missing argument to `%s'", predicate_name);
  187.       else
  188.         error (1, 0, "invalid argument `%s' to `%s'",
  189.            argv[i], predicate_name);
  190.     }
  191.     }
  192.   if (predicates->pred_next == NULL)
  193.     {
  194.       /* No predicates that do something other than set a global variable
  195.      were given; remove the unneeded initial `(' and add `-print'. */
  196.       cur_pred = predicates;
  197.       predicates = last_pred = predicates->pred_next;
  198.       free ((char *) cur_pred);
  199.       parse_print (argv, &argc);
  200.     }
  201.   else if (!no_side_effects (predicates->pred_next))
  202.     {
  203.       /* One or more predicates that produce output were given;
  204.      remove the unneeded initial `('. */
  205.       cur_pred = predicates;
  206.       predicates = predicates->pred_next;
  207.       free ((char *) cur_pred);
  208.     }
  209.   else
  210.     {
  211.       /* `( user-supplied-expression ) -print'. */
  212.       parse_close (argv, &argc);
  213.       parse_print (argv, &argc);
  214.     }
  215.  
  216. #ifdef    DEBUG
  217.   printf ("Predicate List:\n");
  218.   print_list (predicates);
  219. #endif /* DEBUG */
  220.  
  221.   /* Done parsing the predicates.  Build the evaluation tree. */
  222.   cur_pred = predicates;
  223.   eval_tree = get_expr (&cur_pred, NO_PREC);
  224. #ifdef    DEBUG
  225.   printf ("Eval Tree:\n");
  226.   print_tree (eval_tree, 0);
  227. #endif /* DEBUG */
  228.  
  229.   /* Rearrange the eval tree in optimal-predicate order. */
  230.   opt_expr (&eval_tree);
  231.  
  232.   /* Determine the point, if any, at which to stat the file. */
  233.   mark_stat (eval_tree);
  234.  
  235. #ifdef DEBUG
  236.   printf ("Optimized Eval Tree:\n");
  237.   print_tree (eval_tree, 0);
  238. #endif /* DEBUG */
  239.  
  240. #ifndef HAVE_FCHDIR
  241.   starting_dir = xgetcwd ();
  242.   if (starting_dir == NULL)
  243.     error (1, errno, "cannot get current directory");
  244. #else
  245.   starting_desc = open (".", O_RDONLY);
  246.   if (starting_desc < 0)
  247.     error (1, errno, "cannot open current directory");
  248. #endif
  249.  
  250.   /* If no paths are given, default to ".".  */
  251.   for (i = 1; i < argc && strchr ("-!(),", argv[i][0]) == NULL; i++)
  252.     process_top_path (argv[i]);
  253.   if (i == 1)
  254.     process_top_path (".");
  255.  
  256.   exit (exit_status);
  257. }
  258.  
  259. /* Descend PATHNAME, which is a command-line argument.  */
  260.  
  261. static void
  262. process_top_path (pathname)
  263.      char *pathname;
  264. {
  265.   struct stat stat_buf;
  266.  
  267.   curdepth = 0;
  268.   path_length = strlen (pathname);
  269.  
  270.   /* We stat each pathname given on the command-line twice --
  271.      once here and once in process_path.  It's not too bad, though,
  272.      since the kernel can read the stat information out of its inode
  273.      cache the second time.  */
  274.   if ((*xstat) (pathname, &stat_buf) == 0 && S_ISDIR (stat_buf.st_mode))
  275.     {
  276.       if (chdir (pathname) < 0)
  277.     {
  278.       error (0, errno, "%s", pathname);
  279.       exit_status = 1;
  280.       return;
  281.     }
  282.       process_path (pathname, ".", false, ".");
  283. #ifndef HAVE_FCHDIR
  284.       if (chdir (starting_dir) < 0)
  285.     error (1, errno, "%s", starting_dir);
  286. #else
  287.       if (fchdir (starting_desc))
  288.     error (1, errno, "cannot return to starting directory");
  289. #endif
  290.     }
  291.   else
  292.     process_path (pathname, pathname, false, ".");
  293. }
  294.  
  295. /* Info on each directory in the current tree branch, to avoid
  296.    getting stuck in symbolic link loops.  */
  297. struct dir_id
  298. {
  299.   ino_t ino;
  300.   dev_t dev;
  301. };
  302. static struct dir_id *dir_ids = NULL;
  303. /* Entries allocated in `dir_ids'.  */
  304. static int dir_alloc = 0;
  305. /* Index in `dir_ids' of directory currently being searched.
  306.    This is always the last valid entry.  */
  307. static int dir_curr = -1;
  308. /* (Arbitrary) number of entries to grow `dir_ids' by.  */
  309. #define DIR_ALLOC_STEP 32
  310.  
  311. /* Recursively descend path PATHNAME, applying the predicates.
  312.    LEAF is true if PATHNAME is known to be in a directory that has no
  313.    more unexamined subdirectories, and therefore it is not a directory.
  314.    Knowing this allows us to avoid calling stat as long as possible for
  315.    leaf files.
  316.  
  317.    NAME is PATHNAME relative to the current directory.  We access NAME
  318.    but print PATHNAME.
  319.  
  320.    PARENT is the path of the parent of NAME, relative to find's
  321.    starting directory.
  322.  
  323.    Return nonzero iff PATHNAME is a directory. */
  324.  
  325. static int
  326. process_path (pathname, name, leaf, parent)
  327.      char *pathname;
  328.      char *name;
  329.      boolean leaf;
  330.      char *parent;
  331. {
  332.   struct stat stat_buf;
  333.   static dev_t root_dev;    /* Device ID of current argument pathname. */
  334.   int i;
  335.  
  336.   /* Assume it is a non-directory initially. */
  337.   stat_buf.st_mode = 0;
  338.  
  339.   rel_pathname = name;
  340.  
  341.   if (leaf)
  342.     have_stat = false;
  343.   else
  344.     {
  345.       if ((*xstat) (name, &stat_buf) != 0)
  346.     {
  347.       error (0, errno, "%s", pathname);
  348.       exit_status = 1;
  349.       return 0;
  350.     }
  351.       have_stat = true;
  352.     }
  353.  
  354.   if (!S_ISDIR (stat_buf.st_mode))
  355.     {
  356.       if (curdepth >= mindepth)
  357.     apply_predicate (pathname, &stat_buf, eval_tree);
  358.       return 0;
  359.     }
  360.  
  361.   /* From here on, we're working on a directory.  */
  362.  
  363.   stop_at_current_level = maxdepth >= 0 && curdepth >= maxdepth;
  364.  
  365.   /* If we've already seen this directory on this branch,
  366.      don't descend it again.  */
  367.   for (i = 0; i <= dir_curr; i++)
  368.     if (stat_buf.st_ino == dir_ids[i].ino &&
  369.     stat_buf.st_dev == dir_ids[i].dev)
  370.       stop_at_current_level = true;
  371.  
  372.   if (dir_alloc <= ++dir_curr)
  373.     {
  374.       dir_alloc += DIR_ALLOC_STEP;
  375.       dir_ids = (struct dir_id *)
  376.     xrealloc ((char *) dir_ids, dir_alloc * sizeof (struct dir_id));
  377.     }
  378.   dir_ids[dir_curr].ino = stat_buf.st_ino;
  379.   dir_ids[dir_curr].dev = stat_buf.st_dev;
  380.  
  381.   if (stay_on_filesystem)
  382.     {
  383.       if (curdepth == 0)
  384.     root_dev = stat_buf.st_dev;
  385.       else if (stat_buf.st_dev != root_dev)
  386.     stop_at_current_level = true;
  387.     }
  388.  
  389.   if (do_dir_first && curdepth >= mindepth)
  390.     apply_predicate (pathname, &stat_buf, eval_tree);
  391.  
  392.   if (stop_at_current_level == false)
  393.     /* Scan directory on disk. */
  394.     process_dir (pathname, name, strlen (pathname), &stat_buf, parent);
  395.  
  396.   if (do_dir_first == false && curdepth >= mindepth)
  397.     apply_predicate (pathname, &stat_buf, eval_tree);
  398.  
  399.   dir_curr--;
  400.  
  401.   return 1;
  402. }
  403.  
  404. /* Scan directory PATHNAME and recurse through process_path for each entry.
  405.  
  406.    PATHLEN is the length of PATHNAME.
  407.  
  408.    NAME is PATHNAME relative to the current directory.
  409.  
  410.    STATP is the results of *xstat on it.
  411.  
  412.    PARENT is the path of the parent of NAME, relative to find's
  413.    starting directory.  */
  414.  
  415. static void
  416. process_dir (pathname, name, pathlen, statp, parent)
  417.      char *pathname;
  418.      char *name;
  419.      int pathlen;
  420.      struct stat *statp;
  421.      char *parent;
  422. {
  423.   char *name_space;        /* Names of files in PATHNAME. */
  424.   int subdirs_left;        /* Number of unexamined subdirs in PATHNAME. */
  425.  
  426.   subdirs_left = statp->st_nlink - 2; /* Account for name and ".". */
  427.  
  428.   errno = 0;
  429.   /* On some systems (VAX 4.3BSD+NFS), NFS mount points have st_size < 0.  */
  430.   name_space = savedir (name, statp->st_size > 0 ? statp->st_size : 512);
  431.   if (name_space == NULL)
  432.     {
  433.       if (errno)
  434.     {
  435.       error (0, errno, "%s", pathname);
  436.       exit_status = 1;
  437.     }
  438.       else
  439.     error (1, 0, "virtual memory exhausted");
  440.     }
  441.   else
  442.     {
  443.       register char *namep;    /* Current point in `name_space'. */
  444.       char *cur_path;        /* Full path of each file to process. */
  445.       char *cur_name;        /* Base name of each file to process. */
  446.       unsigned cur_path_size;    /* Bytes allocated for `cur_path'. */
  447.       register unsigned file_len; /* Length of each path to process. */
  448.       register unsigned pathname_len; /* PATHLEN plus trailing '/'. */
  449.  
  450.       if (pathname[pathlen - 1] == '/')
  451.     pathname_len = pathlen + 1; /* For '\0'; already have '/'. */
  452.       else
  453.     pathname_len = pathlen + 2; /* For '/' and '\0'. */
  454.       cur_path_size = 0;
  455.       cur_path = NULL;
  456.  
  457.       if (strcmp (name, ".") && chdir (name) < 0)
  458.     {
  459.       error (0, errno, "%s", pathname);
  460.       exit_status = 1;
  461.       return;
  462.     }
  463.  
  464.       for (namep = name_space; *namep; namep += file_len - pathname_len + 1)
  465.     {
  466.       /* Append this directory entry's name to the path being searched. */
  467.       file_len = pathname_len + strlen (namep);
  468.       if (file_len > cur_path_size)
  469.         {
  470.           while (file_len > cur_path_size)
  471.         cur_path_size += 1024;
  472.           if (cur_path)
  473.         free (cur_path);
  474.           cur_path = xmalloc (cur_path_size);
  475.           strcpy (cur_path, pathname);
  476.           cur_path[pathname_len - 2] = '/';
  477.         }
  478.       cur_name = cur_path + pathname_len - 1;
  479.       strcpy (cur_name, namep);
  480.  
  481.       curdepth++;
  482.       if (!no_leaf_check)
  483.         /* Normal case optimization.
  484.            On normal Unix filesystems, a directory that has no
  485.            subdirectories has two links: its name, and ".".  Any
  486.            additional links are to the ".." entries of its
  487.            subdirectories.  Once we have processed as many
  488.            subdirectories as there are additional links, we know
  489.            that the rest of the entries are non-directories --
  490.            in other words, leaf files. */
  491.         subdirs_left -= process_path (cur_path, cur_name,
  492.                       subdirs_left == 0, pathname);
  493.       else
  494.         /* There might be weird (e.g., CD-ROM or MS-DOS) filesystems
  495.            mounted, which don't have Unix-like directory link counts. */
  496.         process_path (cur_path, cur_name, false, pathname);
  497.       curdepth--;
  498.     }
  499.  
  500.       if (strcmp (name, "."))
  501.     {
  502.       if (!dereference)
  503.         {
  504.           if (chdir ("..") < 0)
  505.         /* We could go back and do the next command-line arg instead,
  506.            maybe using longjmp.  */
  507.         error (1, errno, "%s", parent);
  508.         }
  509.       else
  510.         {
  511. #ifndef HAVE_FCHDIR
  512.           if (chdir (starting_dir) || chdir (parent))
  513.         error (1, errno, "%s", parent);
  514. #else
  515.           if (fchdir (starting_desc) || chdir (parent))
  516.         error (1, errno, "%s", parent);
  517. #endif
  518.         }
  519.     }
  520.  
  521.       if (cur_path)
  522.     free (cur_path);
  523.       free (name_space);
  524.     }
  525. }
  526.  
  527. /* Return true if there are no side effects in any of the predicates in
  528.    predicate list PRED, false if there are any. */
  529.  
  530. static boolean
  531. no_side_effects (pred)
  532.      struct predicate *pred;
  533. {
  534.   while (pred != NULL)
  535.     {
  536.       if (pred->side_effects)
  537.     return (false);
  538.       pred = pred->pred_next;
  539.     }
  540.   return (true);
  541. }
  542.